package q131_partition;

import java.util.ArrayList;
import java.util.List;

public class Solution_2 {

    /**
     * 相较于solution1 这里使用模板来解答
     */
    private List<List<String>> res = new ArrayList<>();
    private List<String> path = new ArrayList<>();

    public List<List<String>> partition(String s) {
        dfs(s, 0);
        return res;
    }

    // 设置参数
    private void dfs(String s, int startIndex) {
        // 终止条件
        if (startIndex >= s.length()){
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = startIndex; i < s.length(); i++) {
            // 判断是不是回文字符串
            // 这里只是写的有点不像模版体
            // 实际上是一样的 只是多了一个直接跳过的判断 --> 如下
            // if(){path.add...dfs...path.remove}else{continue}
            if (isPalindrome(s, startIndex, i)){
                path.add(s.substring(startIndex, i + 1));
            }else {
                continue;
            }
            // 回溯
            dfs(s, i + 1);
            // 移除
            path.remove(path.size() - 1);
        }


    }

    private boolean isPalindrome(String s, int startIndex, int endIndex) {

        for (int i = startIndex, j = endIndex; i <= j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) return false;
        }
        return true;
    }
}
